Termity 2
Limit pamięci: 128 MB
Czy pamiętasz jeszcze dwa przyjacielskie sztachetożerne
termity, którym nigdy nie dość rozrywek umysłowych?
Otóż po spałaszowaniu większości płotów w Bajtocji nabrały apetytu na drzewa.
Drzewem nazywamy spójny graf nieskierowany o wierzchołkach i krawędziach.
Naszym dwóm termitom prędko znudziło się monotonne zjadanie wierzchołków - wymyśliły zatem grę,
którą planują urozmaicić sobie posiłek.
Ustaliły pewną kolejność krawędzi drzewa, które zamierzają zjeść.
Gra potrwa co najwyżej rund, w każdej rundzie ruch wykonuje dokładnie jeden termit.
Gracze ruszają się na przemian (zaczynający gra w rundzie , drugi w rundzie ,
w rundzie znów pierwszy, i tak dalej).
W -tej rundzie grający termit musi wybrać dowolny z niezjedzonych końców krawędzi
i go zjeść.
Jeśli oba końce są zjedzone, zanim termit wykona swój ruch, gra kończy się jego przegraną.
Jeśli gra nie skończy się w ciągu rund, ma miejsce remis.
Zakładamy, że (doświadczone przecież w tego typu zabawach) termity grają bezbłędnie,
przy czym termit, który ma strategię umożliwiającą mu zwycięstwo, dąży do wygranej
w możliwie najwcześniejszej rundzie, zaś jego przeciwnik chce przegrać jak najpóźniej.
Twoim zadaniem jest, dla danego drzewa i kolejności jego krawędzi ustalonej przez termity,
określić, w której rundzie skończy się gra.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita
() - liczba wierzchołków drzewa.
W kolejnych wierszach podane są krawędzie drzewa w kolejności ustalonej przez termity.
W -tym z tych wierszy znajdują się dwie liczby całkowite oraz
() - numery końców krawędzi .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą
- numer rundy, w której skończy się gra, lub , jeśli będzie miał miejsce remis.
Przykład
Dla danych wejściowych:
5
2 3
1 2
4 5
3 4
poprawną odpowiedzią jest:
4
Wyjaśnienie do przykładu: Jeśli w pierwszej rundzie zaczynający termit zje wierzchołek ,
zaś w trzeciej rundzie wierzchołek , jego przeciwnik nie będzie miał żadnego ruchu w rundzie
czwartej, niezależnie od tego, jak zagrał w rundzie drugiej.
Autor zadania: Jakub Pachocki.